import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class LeetCode30 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new LinkedList<>();
        int sLen = s.length();
        int wLen = 0;
        Map<String, Integer> hash = new HashMap<>();
        for (String str : words) {
            wLen += str.length();
            hash.put(str, hash.getOrDefault(str, 0) + 1);
        }
        int wide = wLen / words.length;//数组中每个字符串的长度
        for (int i = 0; i < sLen - wLen + 1; i++) {
            String str = s.substring(i, i + wLen);
            if (isSubstring(str, hash, wide)) {
                list.add(i);
            }
        }
        return list;
    }
    public boolean isSubstring(String str, Map<String, Integer> hash, int wide) {
        Map<String, Integer> hash1 = new HashMap<>();
        int sLen = str.length();
        for (int i = 0; i < sLen - wide + 1; i += wide) {
            String str1 = str.substring(i, i + wide);
            hash1.put(str1, hash1.getOrDefault(str1, 0) + 1);
        }
        return hash.equals(hash1);
    }

    public List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> list = new LinkedList<>();
        int sLen = s.length();
        int wLen = 0;
        Map<String, Integer> hash = new HashMap<>();
        for (String str : words) {
            wLen += str.length();
            hash.put(str, hash.getOrDefault(str, 0) + 1);
        }
        int wide = wLen / words.length;//数组中每个字符串的长度
        int n = 0;//记录滑动窗口执行的次数，要小于wide
        while (n < wide) {
            Map<String, Integer> hash1 = new HashMap<>();
            for (int left = n, right = n, count = 0; right < sLen && right + wide <= sLen; right += wide) {
                String str = s.substring(right, right + wide);
                hash1.put(str, hash1.getOrDefault(str, 0) + 1);
                if (hash1.get(str) <= hash.getOrDefault(str, 0)) {
                    count++;
                }
                if (right - left >= wLen) {
                    String str1 = s.substring(left, left + wide);
                    if (hash.get(str1) != null && hash1.get(str1) <= hash.get(str1)) {
                        count--;
                    }
                    hash1.put(str1, hash1.getOrDefault(str1, 0) - 1);
                    left += wide;
                }
                if (count == words.length) {
                    list.add(left);
                }
            }
            n++;
        }
        // Map<String, Integer> hash1 = new HashMap<>();
        // for (int left = 0, right = 0, count = 0; right < sLen; right += wide) {
        //     String str = s.substring(right, right + wide);
        //     hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        //     if (hash1.get(str) <= hash.getOrDefault(str, 0)) {
        //         count++;
        //     }
        //     if (right - left >= wLen) {
        //         String str1 = s.substring(left, left + wide);
        //         if (hash.get(str1) != null && hash1.get(str1) <= hash.get(str1)) {
        //             count--;
        //         }
        //         hash1.put(str1, hash1.getOrDefault(str1, 0) - 1);
        //         left += wide;
        //     }
        //     if (count == words.length) {
        //         list.add(left);
        //     }
        // }
        return list;
    }
}
